package com.gzl.exercise;

import org.junit.jupiter.api.Test;
import org.springframework.boot.test.context.SpringBootTest;

import java.util.Arrays;
import java.util.Scanner;  //必须先在类头添加这个才能运用输入功能

//@SpringBootTest
/**
 * @PROJECT_NAME: exercise
 * @NAME: 最小操作数
 * @DESCRIPTION: 中等
 * @USER: gaozengliang
 * @DATE: 2023/3/27
 */
class 最小操作数 {

    /*
    最小操作次数使数组元素相等
        给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。
        示例 1：
        输入：nums = [1,2,3]
        输出：3
        解释：
        只需要3次操作（注意每次操作会增加两个元素的值）：
        [1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

        示例 2：
        输入：nums = [1,1,1]
        输出：0

        提示：
        n == nums.length
        1 <= nums.length <= 105
        -10^9 <= nums[i] <= 10^9
        答案保证符合 32-bit 整数
    * */
    // 优化
    /**
     * 分析1：
     * 每次n-1个元素加1，直至相等，假如总共操作了x次，也就是数组的总和 sum 加了 (n-1)*k,
     * 在整个流程的每次操作中，最小的那个值都会增加 1 。
     * 由贪心可知，经过k 步后， min 变为了 min + k ，也意味着此时数组的每一项都变为了 min + k ，所以操作结束后数组的和为 n * (min + k) 。
     * 根据等量代换：
     * sum + k * (n - 1) = n * (min + k)
     * sum + k * n - k = n * min + n * k
     * sum - k = n * min
     * k = sum - n * min
     * 所以，最短操作次数为 k = sum - n * min 。
     * 先求和再减去长度n个最小值，不是相当于每一项减去最小值再求和吗？
     */
    /**
     * 分析2：反向思维
     *  n-1个元素加一，也就是一个元素减一，直至减到所有元素都相等，与最小的都相等
     *  每个元素的值减至和最小元素的值相等所需的次数，就是操作次数
     */
    @Test
    void minMovesTest2(){
        int[] nums = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1000000000};
        int sum = 0;
        int min = nums[0];
        // 找出最小的元素
        /*for (int i=1;i<nums.length;i++){
            if (nums[i]<min){
                min = nums[i];
            }
        }*/
        // 找出最小的元素
        int minNum = Arrays.stream(nums).min().getAsInt();

        // 计算所有元素减至与最小元素相等时所需的次数
        /*for (int i=0;i<nums.length;i++){
            if (nums[i]>min){
                sum = sum+(nums[i]-min);
            }
        }*/
        for (int num:nums){
            if (num > min){
                sum +=num - min;
            }
        }
        System.out.println(sum);
    }
    // 该方法当数值过大的时候，如数组{1,1000000000},运算时间极长，虽然能得到正确结果，但是时间会超出限制，不通过。
    @Test
    void minMovesTest1(){
        int[] nums = {1,1000000000};
//        int[] nums = {1,2,3,4,5};
        int nl = nums.length; // 数组长度
        int max; // 数组最大值
        int maxid; // 数组最大值的序号
        int t = 0; // 操作次数
        boolean flag; // 记录是否都相等的标志
        while (1 == 1){
            // 重置标志为 false
            flag = true;
            for(int i=0;i<nl-1;i++){
                if (nums[i]!=nums[i+1]){
                    // 如果有不相等的元素就跳出循环，标记设为false
                    flag = false;
                    break;
                }
            }
            // 数组内元素都相等了，结束循环，此次运算结束。
            if (flag){
                // 输出最小操作次数
                System.out.println(t);
                break;
            }else {
                // 数组内元素还未都相等，继续运算。
                max = nums[0];
                maxid = 0;
                // 寻找数组内最大的元素及其下标
                for (int i=0;i<nl;i++){
                    if (nums[i]>=max){
                        max = nums[i];
                        maxid = i;
                    }
                }
                // 除最大的元素外，其它元素值加一
                for (int i=0;i<nl;i++){
                    if (i != maxid){
                        nums[i]++;
                    }
                }
                // 记录操作数
                t++;
            }
        }
    }


    public static void main(String[] args) {
        //创建一个扫描器对象，用于接收键盘数据
        Scanner scanner = new Scanner(System.in);
        //next方式接收字符串(不可以接收空格)
        System.out.println("请输入:");
        //判断用户还有没有输入字符
        /*if (scanner.hasNext()) {
            String str = scanner.next();
            System.out.println("输入内容：" + str);
        }*/
        if (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            System.out.println("输入内容：" + str);
            String[] strs=str.split(",");
            int[] nums = new int[strs.length];
            for (int i=0;i<strs.length;i++){
                nums[i] = Integer.parseInt(strs[i]);
            }
        }
        // 凡是属于IO流的类如果不关闭会一直占用资源.要养成好习惯用完就关掉.
        // 就好像你接水完了要关水龙头一样.很多下载软件或者视频软件如果你不彻底关，都会自己上传下载从而占用资源，你就会觉得 卡，这是一个道理.
        scanner.close();
    }

}
